package com.copa.l215;

/**
 * @author copa
 * @createDate 2022-05-29 18:30
 * @function 快速排序法
 */
public class Test3 {

    public int findKthLargest(int[] nums, int k) {
        // 从nums整个数组进行快速排序
        return quickSort(nums, 0, nums.length - 1, k);
    }

    private int quickSort(int[] nums, int left, int right, int k) {
        // 随机取一个数，分区后所得到左指针index
        int index = randomPartition(nums, left, right);
        if (index == k - 1) {
            // 若符合条件，此时就是第k大的数
            return nums[index];
        }
        // 分区范围划分，寻找符合分区的条件，不符合条件的就没必要往那个范围再次快排
        return index > k - 1
                ? quickSort(nums, left, index - 1, k)
                : quickSort(nums, index + 1, right, k);
    }

    private int randomPartition(int[] nums, int left, int right) {
        // 这里随机取一个数进行比对
        int i = (int) (Math.random() * (right - left)) + left;
        // 跟当前的右进行交换指针，方便接下来作为基准数
        swap(nums, i, right);
        // 进行快排分区
        return partition(nums, left, right);
    }

    private void swap(int[] nums, int i, int j) {
        // 两两交换
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private int partition(int[] nums, int left, int right) {
        // 这里设定基准数
        int pivot = nums[right];
        // 防止右指针发生变化，需要将其记录
        int rightMost = right;
        // 如果左指针 <= 右指针 需要分区处理
        while (left <= right) {
            // 如果左指针指向的数比基准数大
            while (left <= right && nums[left] > pivot) {
                left++;
            }
            // 如果右指针指向的数比基准数小或相等
            while (left <= right && nums[right] <= pivot) {
                right--;
            }
            if (left <= right) {
                // 如果此时left指针还是小于等于right指针，则进行交换
                swap(nums, left, right);
            }
        }
        // 分区结束，需要把基准数跟左指针调换，这样保证左边永远是大于基准数，右边永远是小于基准数
        swap(nums, left, rightMost);
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {3,2,1,5,6,4};
        System.out.println(new Test3().findKthLargest(nums, 2));
    }
}
